La Macchina di Turing (MT)
Un dispositivo astratto _ una macchina nella quale non vengono presi in considerazione i vincoli necessari ad una sua realizzazione pratica:
- Dimensioni della memoria
- Tempo di calcolo
- Spazio di calcolo
- Indipendenza dalla realizzazione fisica
La MT si definisce per le relazioni funzionali tra le sue parti, non per la sua realizzabilit_.